No.911 ラッキーソート

未完

桁DPが使えたりするらしい。

問題文

長さNの数列Aがあり, どの2つの要素も互いに異なります。

次の操作をちょうど1回行います。

L以上R以下の整数xを選ぶ。

数列のすべての要素をそれぞれxとXORしたものに置き換える。

操作によって数列を狭義単調増加にするxは何通りあるか求めてください。

考察

上位bitから順番に考えていく…、という考え方が役に立つそうです。

まず、数列のそれぞれの要素を2進数で表記すると、

10100110100

10100110111

10100110110

10100110001

10100110000

10100110011

という風になります。

例1を例にして考えてみましょう。

左から1桁目だけを取り出すと、{1,1,1,1,1,1,1}となっています。この部分は、0をxorしても1をxorしても、矛盾が発生しません。

逆に、右から3桁目{1,1,1,0,0,0}は、1をxorして{0,0,0,1,1,1}としないと、その部分では単調増加にならないということが分かります。

パターンは4種類ある

1でも0でもok！

0じゃないとダメ！

1じゃないとダメ！

どっちでも無理！

この場合、それ以降のビット関係なしに無理になるので、その無理になった桁以前で単調増加なやつを返せば良い

サンプルコード(人のやつを改変、自分用コメント)

code:sample.cpp

using namespace std;

typedef long long int ll;

int main() {

// 入力

int N;

ll L, R;

cin >> N >> L >> R;

vector<ll> A(N);

// 左からj桁目は何にするべきか

vector<int> must(61, -1);

for (int i = 0; i + 1 < N; ++i) {

for (int j = 60; j >= 0; --j) { // 上のビットから見ていく

if (x == y) continue; // どっちでもok

break;

}

}

// 桁DPをします

// i桁目まで考えた時何通りあるか？（未満フラグあり）

vector<vector<ll>> dp(62, vector<ll>(2));

for (int i = 0; i <= 60; ++i) {

vector<int> choices; // 選択肢

choices = {0, 1};

else // 必ず0/1を選ばなければならない

for (int l = 0; l <= 1; ++l) { // ub以下が確定しているか?

int v = ub >> 60 - i & 1; // 上限の数字を2進表記した時、左からi桁目のbit

for (int d : choices) {

if (!l && v < d) continue; // ubを超えるなら、遷移しない

}

}

}

};

cout << calc(R) - calc(L - 1) << endl;

}

code:experiment.cpp

using namespace std;

typedef long long int ll;

ll MOD = 1000000007;

ll INFL = 1ll << 60;

ll INF = 1 << 28;

// ====================================================================

int main() {

int n, a, b;

cin >> n >> a >> b;

vector<int> v(n);

for (int i = 0; i < n; i++) {

}

}